package 数据结构;

public class WordDictionary {

    Node root = new Node();
    public WordDictionary() {

    }
    public void addWord(String word) {
        Node p = root;
        for(int i = 0; i < word.length(); ++i){
            int n = word.charAt(i)-'a';
            if(p.children[n]==null)
                p.children[n] = new Node();
            p = p.children[n];
        }
        p.isEnd=true;
    }

    public boolean search(String word) {
        return dfs(word,root,0);
    }

    boolean dfs(String word,Node root ,int index){
        if(index == word.length())
            return root.isEnd;
        char c = word.charAt(index);
        if(c == '.'){
            for(int i = 0; i < 26; ++i){
                if(root.children[i]!=null)
                    return dfs(word,root.children[i],index+1);
            }
        }
        else{
            int n = c-'a';
            if(root.children[n]!=null)
                return dfs(word,root.children[n],index+1);
        }
        return false;
    }
    class Node{
        Node[] children = new Node[26];
        boolean isEnd = false;
    }
}
